package algocasts;

import java.util.PriorityQueue;
import java.util.Queue;

public class P90_mergeKSortedLists {
    class ListNode {
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    private ListNode mergeTwoSortedLists(ListNode l1, ListNode l2) {
        ListNode vnode = new ListNode(0), p = vnode;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                p.next = l1;
                l1 = l1.next;
            } else {
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        if (l1 != null) p.next = l1;
        if (l2 != null) p.next = l2;
        return vnode.next;
    }

    // Time: O(k*n)  Space: O(1)
    public ListNode mergeKLists_OneByOne(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        ListNode res = null;
        for (ListNode list : lists)
            res = mergeTwoSortedLists(list, res);
        return res;
    }

    public ListNode mergeKLists_MinHeap(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        Queue<ListNode> q = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode list : lists)
            if (list != null)
                q.add(list);
        ListNode vnode = new ListNode(0), p = vnode;
        while (!q.isEmpty()) {
            ListNode min = q.poll();
            p.next = min;
            p = p.next;
            if (min.next != null) q.add(min.next);
        }
        return vnode.next;
    }

    //
    private ListNode merge(ListNode[] lists, int start, int end) {
        if (start == end) return lists[start];
        if (start > end) return null;
        int mid = start + (end - start) / 2;
        ListNode left = merge(lists, start, mid);
        ListNode right = merge(lists, mid + 1, end);
        return mergeTwoSortedLists(left, right);
    }

    public ListNode mergeKLists_DivideConquer(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        return merge(lists, 0, lists.length - 1);
    }

}
